package ahot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class ListMerge {
    //    给定两个允许有相同元素的升序数组，
//    合并这两个数组到一个新数组中，当有多个相同元素时，
//    清除这些元素，要求不能使用 map 或者字典。
//    例如 listA = [1,1,1,2,3,4]，listB = [3,5,6]，则合并后的数组为 [2,4,5,6]
//    [1,1,1, ]
    public ArrayList<Integer> merge(ArrayList<Integer> listA, ArrayList<Integer> listB) {
        ArrayList<Integer> ans = new ArrayList<>();
        int p1 = 0;
        int p2 = 0;
        while (p1 < listA.size() - 1 && p2 < listB.size() - 1) {

            Integer i1 = listA.get(p1);
            Integer i2 = listB.get(p2);

            Integer addTemp = 0;
            if (i1 < i2) {
                addTemp = i1;
                p1++;
            } else {
                addTemp = i2;
                p2++;
            }

            if (Objects.equals(ans.get(ans.size() - 1), addTemp)) {
                ans = dealWithDup(ans, addTemp);
            } else {
                ans.add(addTemp);
            }
        }

        // 对多余的，没处理完的数据做剩下的拼接。
        while (p1 < listA.size()) {
            Integer addTemp = listA.get(p1);
            if (Objects.equals(ans.get(ans.size() - 1), addTemp)) {
                ans = dealWithDup(ans, addTemp);
            } else {
                ans.add(addTemp);
            }

            p1++;
        }

        while (p2 < listB.size()) {
            Integer addTemp = listB.get(p2);
            if (Objects.equals(ans.get(ans.size() - 1), addTemp)) {
                ans = dealWithDup(ans, addTemp);
            } else {
                ans.add(addTemp);
            }
            p2++;
        }

        return ans;
    }

    // 相同元素时，清除这些元素。
    private ArrayList<Integer> dealWithDup(ArrayList<Integer> ans, Integer addTemp) {
        for (int i = ans.size() - 1; i > 0; i--) {
            if (Objects.equals(ans.get(i), addTemp)) {
                ans.remove(i);
            }
        }
        return ans;
    }


//    给定两个允许有相同元素的升序数组，合并这两个数组到一个新数组中，当有多个相同元素时，清除这些元素，
//    要求不能使用 map 或者字典。例如 listA = [1,1,2,3,4,6]，listB = [3,5,6]，则合并后的数组为 [2,4,5,6]。
//    首先这个题目看到的时候，正常就是力扣上的一个题目：合并两个升序数组。
//    但是也有不同之处，就是升序之后我们要去除重复的元素。整体上就是先合并两个升序数组，然后再清除重复的元素。
//    合并升序数组的思路：
//    因为两个数组都是有序的，所以两个数组内之间的元素就不用再排序了，我们至需要比较这两个数组内的元素大小。举例说明：A数组中的1 和 B数组中的3 比较，哪个数组小，就移动哪个数组下标位置，1 < 3, 则A数组下标移动，继续比较A数组中下一个 1 < 3, 再比较 2<3 ,再比较 3= 3，继续移动A数组指针，4 > 3, 此时移动B数组下标到 5， 4<5 ....以此类推。我们在每次比较的过程中将小的数组元素放入到一个新的数组中，这样就完成了合并两个升序数组。

    public void merge(int[] A, int m, int[] B, int n) {
        int [] result = new int[m+n];
        int acur = 0;
        int bcur = 0;
        while(acur < m || bcur < n){
            if (acur < m && bcur < n) {
                //A数组和B数组均未遍历到尾部
                if (A[acur] <= B[bcur]) {
                    result[acur + bcur] = A[acur];
                    acur++;
                } else{
                    result[acur + bcur] = B[acur];
                    bcur++;
                }
            } else if (bcur < n) {
                //A数组遍历到尾部了
                result[acur+bcur] = B[bcur];
                bcur++;
            } else if (acur < m) {
                result[acur+bcur] = A[acur];
                acur++;
                //B数组遍历到尾部
            }
        }
    }
//    去除重复元素的思路：
//    首先合并后的数组是升序的，所以重复元素是相邻的。我们只需要比较相邻的两个元素，如果相同，则遍历这个数组，从相同元素下标开始遍历，找到所有相同元素，数组元素值置为0。 再继续比较相邻元素，相同再遍历数组，元素值置为0，依次类推。


    public static void main(String[] args) {
        int[] result = {1,1,2,2,2,3,5,6,6};
        int left = 0;
        int right = 1;

        ArrayList<Integer> noRepeatResult = new ArrayList<>();
        // 1,1,2,2,2,3,5,6,6
        while (right < result.length) {
            if (result[left] == result[right]) {
                int x = result[left];
                int count = 0;
                for (int i = left; i < result.length; i++) {
                    if (result[i] == x) {
                        result[i] = 0;
                        count++;
                    } else {
                        break;
                    }
                }
                left += count;
                right = left + 1;
            } else {
                noRepeatResult.add(result[left]);
                left++;
                right++;
            }
        }

        int[] ans = new int[noRepeatResult.size()];
        for (int i = 0; i < noRepeatResult.size(); i++) {
            ans[i] = noRepeatResult.get(i);
        }
        System.out.println( Arrays.toString(ans));

    }


//    作者：ershuai8614
//    链接：https://www.jianshu.com/p/b9c6849379d2
//    来源：简书
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
